/**
 * describe:
 *
 * @author chaP
 * @date 2018/12/25
 */
package CodingTest.AC20190317;

/**
 * 合并两个链表的递归和非递归方法
 */
public class mergeTwoSortLinklist {
    class ListNode{
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
  //非递归算法
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        ListNode dump = new ListNode(0);
        ListNode head = dump;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        while(l1.next != null&&l2.next != null){
            if(l1.val <= l2.val){
                head = l1;
                head = head.next;
                l1 = l1.next;
            }else {
                head = l2;
                head = head.next;
                l2 = l2.next;
            }
        }
        if(l1 == null ){
            head = l2;
        }else{
            head = l1;
        }
        return dump.next;
    }
    public ListNode mergeTwoLists2(ListNode l1,ListNode l2){
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;
        ListNode head = null;
        if(l1.val<= l2.val){
            head = l1;
            head.next =  mergeTwoLists2(l1.next,l2);
        }else{
            head = l2;
            head.next =mergeTwoLists2(l1,l2.next);
        }
        return head;


    }
}
